package com.lql.algorithm;

import java.util.Arrays;

/**
 * 背包问题
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3, 5};//商品重量
        int[] val = {1500, 3000, 2000, 1000};//商品价值
        int m = 4;//背包容量
        int[][] v = new int[val.length + 1][m + 1];
        int[][] path = new int[val.length + 1][m + 1];//记录放入物品路径

        //将第一行、第一列初始化为0
        Arrays.stream(v).forEach((item) -> {
            item[0] = 0;
        });
        Arrays.fill(v[0], 0);

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                if (w[i - 1] > j) {
                    //放入的当前商品重量大于背包剩余容量
                    v[i][j] = v[i - 1][j];
                } else {
                    //当前商品重量小于等于背包剩余重量
//                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    if (v[i - 1][j] > val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = v[i - 1][j];
                    } else {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        path[i][j] = 1;
                    }
                }
            }
        }


        //打印v
        Arrays.stream(v).forEach((item) -> {
            Arrays.stream(item).forEach((item2) -> {
                System.out.print(item2 + "  ");
            });
            System.out.println();
        });

        //打印路径
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.println("第" + i + "个商品放入背包");
                j -= w[i - 1];
            }
            i--;
        }
    }
}
